package homework1_array.alg_65;

import static homework1_array.Utils.printList;

public class ArrayHomework {

    public static void main(String[] args) {

        //todo 作业1：完成这个测试方法中的addByElementBySequence()方法
        arrayAddTest();

        // todo 作业2：完成这个测试类中的removeByElement()方法
        deleteTest();

    }

    /**
     * 在有序列表中插入元素
     */
    private static void arrayAddTest() {

        int[] arr = new int[20];
        arr[0] = 3;
        arr[1] = 4;
        arr[2] = 7;
        arr[3] = 8;
        // 1.中间位置插入
        addByElementSequence(arr, 4, 6);
        printList("在有序数组的中间部分插入元素后的结果为：", arr, 5);
        //此时应输出 3 4 6 7 8

        //2.尾部插入
        addByElementSequence(arr, 5, 9);
        printList("在有序数组的尾部插入元素后的结果为：", arr, 6);
        //此时应输出 3 4 6 7 8 9

        //3.数组首部插入
        addByElementSequence(arr, 6, 1);
        printList("在有序数组的首部部分插入元素后的结果为：", arr, 7);
        //此时应输出：1 3 4 6 7 8 9

    }

    //todo 作业1：完成这个方法

    /**
     * @param arr     存储元素的数组
     * @param size    数组中已经存储的元素数量
     * @param element 要插入数组的新元素
     * @return
     */
    public static void addByElementSequence(int[] arr, int size, int element) {
        //1.检查 size 已否已经达到最大值
        if (size == arr.length) {
            throw new IndexOutOfBoundsException("数组长度已达到最大值:" + arr.length);
        }
        //2.检查 size 是否为 0
        if (size == 0) {
            arr[0] = element;
            size++;
        }
        //3.一般情况,需要找到当前元素在有序数组中的位置,然后将其插入进去.
        int index = getNewElementShouldIndex(arr, size, element);
        //3.1.如果是尾部直接追加即可
        if (index == size) {
            arr[size] = element;
        } else {
            //3.2.非尾部
            // 备份被插入位置的原值 (如果下标和 size大小相同,则为尾部插入)
            int temp = arr[index];
            //开始插入新元素,先扩容一个长度
            size++;
            //新值覆盖旧值
            arr[index] = element;
            //迁移数组:插入位置后的所有元素,往后挪一位,如下所示
            // 3 4 [7] 8
            // 3 4 [6] 7 8
            // 对应的下标
            // 0 1 [2] 3 4
            moveBackArray(arr, index + 1, size - 1);
            // 备份的值往后移一位
            arr[index + 1] = temp;
        }
    }

    /**
     * 往后移动
     *
     * @param arr   有序数组
     * @param start 开始下标
     * @param end   结束下标
     */
    public static void moveBackArray(int[] arr, int start, int end) {
        for (int i = end; i > start; i--) {
            arr[i] = arr[i - 1];
        }
    }

    /**
     * 找到新元素在有序数组中应该所处的位置下表
     *
     * @param arr     有序数组
     * @param size    数组中已经存储的元素数量
     * @param element 要插入数组的新元素
     * @return 下标
     */
    public static int getNewElementShouldIndex(int[] arr, int size, int element) {
        // 举例:在 1 2 3 5 7 8 9 插入 4 ,则第一个比 4 大的元素则为目标位置,返回其下标即可
        for (int i = 0; i < size; i++) {
            if (arr[i] > element) return i;
        }
        //若遍历整个 size 大小的范围都没有比 ele 大的,则追加在尾部,目标位置的下标即为 size
        // 举例:在 1 2 3 5 7 8 9 插入 10,则应追加在尾部
        return size;
    }

    /**
     * 删除测试
     */
    private static void deleteTest() {
        int[] arr = new int[]{2, 3, 4, 9, 10, 11, 12};

        //1.删除头元素
        removeByElement(arr, 7, 2);
        printList("删除头元素后的结果为：", arr, 6);
        //此时应该打印 3 4 9 10 11 12

        //2. 删除尾元素
        removeByElement(arr, 6, 12);
        printList("删除尾元素的结果为：", arr, 5);
        //此时应该打印 3 4 9 10 11

        //3. 删除中间元素：
        removeByElement(arr, 5, 9);
        printList("删除中间元素的结果为：", arr, 4);
        //此时应该打印 3 4 10 11
    }

    /**
     * 从数组中删除元素e
     *
     * @param arr  数组
     * @param size 数组已经存放的元素大小
     * @param key  要删除的元素
     */
    public static void removeByElement(int[] arr, int size, int key) {
        //1.数组是否已经为空
        if (size == 0) {
            throw new RuntimeException("数组元素已空");
        }
        //2.找到元素对应的下标
        int index = getShouldDeleteIndex(arr, size, key);
        //3.如果此元素不存在数组中,那直接结束
        if (index == -1) {
            return;
        }
        //4.如果是尾部
        if ((size - 1) == index) {
            arr[index] = 0;
        } else {
            //迁移数组:插入位置后的所有元素,往后挪一位,如下所示
            // 3 4 [7] 8 9
            // 3 4 [8] 9
            // 对应的下标
            // 0 1 [2] 3
            moveForwardArray(arr, index, size - 1);
        }
    }

    /**
     * 往后移动
     *
     * @param arr   有序数组
     * @param start 开始下标
     * @param end   结束下标
     */
    private static void moveForwardArray(int[] arr, int start, int end) {
        for (int i = start; i < end; i++) {
            arr[i] = arr[i + 1];
        }
    }

    /**
     * 找到元素对应的下标
     *
     * @param arr  数组
     * @param size 数组已经存放的元素大小
     * @param key  要删除的元素
     * @return 下标
     */
    private static int getShouldDeleteIndex(int[] arr, int size, int key) {
        for (int i = 0; i < size; i++) {
            if (arr[i] == key) return i;
        }
        //找不到返回-1
        return -1;
    }
}
